/********************************
 * Robinson Matrix Algorithm
 *
 * Copyright (C) 2009 CNRS
 * Author : Florent AVELLANEDA, Eugen CEPOI
 * 
 *
 * All rights reserved.
 *
 *   This file is part of Robinson Matrix Algorithm.
 *
 *   Robinson Matrix Algorithm is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   Robinson Matrix Algorithm is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with Robinson Matrix Algorithm.  If not, see <http://www.gnu.org/licenses/>.
 *
 ***********************************************************************************/
#include "Util.h"

#include <cassert>

namespace Util
{
    bool calculateMaximalChain( std::vector< std::set<unsigned int> > &G, unsigned int begin, unsigned int end, std::vector<unsigned int> &result )
    {
        std::vector<unsigned int> prec;
        std::vector<unsigned int> dist;
        std::set<unsigned int> gris;

        if(G.size() == 0)
            return true;

        dist.resize(G.size());
        prec.resize(G.size(), -1);

        if( !maximalChainRec(G, begin, 0, gris, prec, dist) )
            return false;
        /*
           unsigned int maxDist = dist[ end ];
           result.resize( maxDist );


           while( begin != end )
           {
           result[ --maxDist ] = end;
           end = prec[end];
           if(end == -1)
           return false; // no solution TODO : verifier que ce cas peu se produire et que se soit pas un bug
           }
           result[ --maxDist ] = end;

           assert( maxDist==0 );
           */

        // TODO : FAIRE PLUS PROPREMENT
        std::vector<unsigned int> result2;

        while( begin != end )
        {
            result2.push_back( end );
            end = prec[end];
        }
        result2.push_back( end );

        while( result2.size() > 0 )
        {
            result.push_back( result2.back() );
            result2.pop_back();
        }

        return true;
    }

    bool calculateMaximalChain( std::vector< std::set<unsigned int> > &G, std::vector<unsigned int> &result )
    {
        std::vector< std::set<unsigned int> > G2 = G;
        std::vector<unsigned int> tmp;

        G2.push_back( std::set<unsigned int>() );
        G2.push_back( std::set<unsigned int>() );

        for (unsigned int i = 0; i < G2.size(); i++)
        {
            if( i != (G2.size()-1) )
                G2[i].insert( G2.size()-1 );
            if( i != (G2.size()-2) )
                G2[ G2.size()-2 ].insert( i );
        }

        if(!calculateMaximalChain( G2, G2.size()-2, G2.size()-1, tmp ))
            return false;

        result.reserve( tmp.size() -2 );

        for (unsigned int i = 1; i < tmp.size()-1; i++)
            result.push_back( tmp[i] );

        return true;
    }


    bool isAcyclique(std::vector< std::set<unsigned int> > &G)
    {
        for (unsigned int i = 0; i < G.size(); i++)
        {
            std::vector<unsigned int> prec;
            std::vector<unsigned int> dist;
            std::set<unsigned int> gris;

            dist.resize(G.size());
            prec.resize(G.size(), -1);

            if( maximalChainRec(G, i, 0, gris, prec, dist) == false )
                return false;
        }
        return true;
    }


    bool maximalChainRec( std::vector< std::set<unsigned int> > &G, unsigned int noeud, unsigned int val, std::set<unsigned int> &gris, std::vector<unsigned int> &prec, std::vector<unsigned int> &dist)
    {
        assert( dist[noeud] <= val );

        // Verification de boucle
        if( gris.count(noeud) > 0 )
            return false;
        gris.insert( noeud );


        dist[noeud] = val;


        for (std::set<unsigned int>::iterator it = G[noeud].begin(); it != G[noeud].end(); ++it)
        {
            if( dist[*it] < (val+1) )
            {
                if( !maximalChainRec( G, *it, val+1, gris, prec, dist ) )
                    return false;
                prec[*it] = noeud;
            }
        }

        gris.erase( noeud );

        return true;
    }


    std::vector<unsigned int> notIn( std::set<unsigned int> &elements, std::vector<unsigned int> &vect)
    {
        std::vector<unsigned int> Xo;
        unsigned int j;

        for ( std::set<unsigned int>::iterator i = elements.begin(); i != elements.end(); ++i )
        {	
            for ( j = 0; j < vect.size(); ++j )
            {
                if ( vect[j] == (*i) )
                    break;
            }
            if ( j == vect.size() )
                Xo.push_back(*i);
        }
        return Xo;
    }

    double dabs(double a)
    {
        return a>0?a:-a;
    }

    double max( double a, double b)
    {
        return a>b?a:b;
    }

    double min( double a, double b)
    {
        return a<b?a:b;
    }
}
